\begin{lemma} \label{lem:halfspace}
If $t$, $b$, $t_i$, $b_i$, $y_i$, $z_i$, (for $1 \le i \le n$), are
$\beta$-bit integers, then either $\sum_{i=1}^n
\frac{t_{i}y_{i}}{b_i z_{i}} \geq \frac{t}{b}$ or
$\sum_{i=1}^n \frac{t_i y_{i}}{b_i z_i} < \frac{t}{b} - \frac{1}{2^{3n\beta}}$.
\end{lemma}

\begin{proof}
Suppose we have $\sum_{i=1}^n \frac{t_i y_{i}}{b_i z_i} <
\frac{t}{b}$.  Then the difference $\frac{t}{b} - \sum_{i=1}^n
\frac{t_i y_{i}}{b_i z_i}$ is at least $1/(b \cdot \prod_i b_i \prod_i
z_i)$, which is at least $1/2^{\beta + 2n\beta} < 2^{-3n\beta}$ since
each integer in the product is at most $2^\beta$.
\end{proof}

From Lemma \ref{lem:halfspace}, we get the following. If $x$ satisfies $\sum_{i=1}^n a_i x_i \geq b -
\frac{1}{2^{3n\beta}}$, where each $a_i$ and $b$ are rational numbers
whose numerators and denominators are representable as $\beta$-bit
integers, then $x$ satisfies $\sum_{i=1}^n a_i x_i \geq b$. This immediately implies the Lemma.
